import java.util.Stack;

/**
 * Created by L.jp
 * Description:给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，
 * 仅仅会存在一个最长的公共子序列
 *
 * 数据范围：0 \le |str1|,|str2| \le 20000≤∣str1∣,∣str2∣≤2000
 * 要求：空间复杂度 O(n^2)O(n^2)
 * ，时间复杂度 O(n^2)O(n^2)
 * 示例1
 * 输入：
 * "1A2C3D4B56","B1D23A456A"
 * 返回值：
 * "123456"
 * 示例2
 * 输入：
 * "abc","def"
 * 返回值：
 * "-1"
 * 示例3
 * 输入：
 * "abc","abc"
 * 返回值：
 * "abc"
 * 示例4
 * 输入：
 * "ab",""
 * 返回值：
 * "-1"
 * User: 86189
 * Date: 2022-04-28
 * Time: 11:56
 */
public class Solution {
    /*      这是最长公共子序列的进阶版，基础版是只需要求出最长公共子序列的长度，而这个题目是需要得到最长公共子序列，
            且示例给出的最长公共子序列中只会有一个。
            对于这个题目，还是有两种做法，
            一种就是不求最长公共子序列的长度，直接利用动规思想用一个字符串类型的动规数组
            保存每一个阶段的最长公共子序列，判断方法是和求最长公共子序列的长度是一样的，就是
            ①：当s1[i-1]==s2[j-1]时
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
             ·
            ②：当s1[i-1]！=s2[j-1]时
            dp[i][j]=dp[i-1][j].length() > dp[i][j-1].length() ?  dp[i][j-1] : dp[i-1][j];
            
            还有一种做法就是先求出最长公共子序列的长度，然后在动规数组中返回去拼接s1和s2对应位置相等的字符，
            因为是公共子序列，所以我们只找对应位置相等的做字符，也就是说只要找到了相等的字符，我们可以使用StringBuilder拼接它，
            还可以使用一个栈来把它存起来，等所有的相等的字符都找到之后，把StringBuilder的内容倒置转成字符串就行了，对于栈的话，就是不断
            弹出栈顶元素，使用字符串拼接起来即可，直到栈为空。
            
            那么关键是如何找到对应位置相等的字符，我们从最长公共子序列的位置开始找，也就是从最后一个位置开始找
            有两种找法，
                ①：一种是通过判断s1[i-1]==s2[j-1]，如果相等就说明当前字符是被算入在最长公共子序列的，
                并且它是由s1的前i-1个字符和s2的前j-1个字符得来的，也就是dp[i-1][j-1]+1;
                所以就拼接当前字符，拼接完之后就从i--,j--的位置开始搜索，这个跟我们计算最长公共子序列的时候是一样的，只不过现在是一个逆过程而已
                如果s1[i-1]!=s2[j-1],那么说明当前最长公共子序列的长度dp[i][j]是由dp[i][j-1]和dp[i-1][j]其中的最大值决定的
                所以如果dp[i-1][j]>dp[i][j-1]，那么说明最长公共子序列是由当前位置的上方的结果得到的，执行i--,反之，说明最长公共
                子序列的长度是由当前位置的左边结果得到我的，执行j--,就这样一直重复搜索，直到找到相等的位置就拼接，
                如果横坐标或者纵坐标其中一个等于0了，那么说明拼接完了，没有字符拼接了
                
                ②：第二种是借助栈来存储公共字符，还是从最后一个位置找起，如果当前位置的最长公共子序列dp[i][j]等于上一个位置的
                最长公共子序列dp[i-1][j]，那么说明最长公共子序列的结果是由它得来的，在他的基础上往回找，执行i--
                如果dp[i][j]==dp[i][j-1]，那么说明最长公共子序列的结果是由他的左边结果得来的，所以执行j--
                如果dp[i][j]>dp[i-1][j-1],那么说明最长公共子序列的长度是由他的左上方结果得到的，所以执行i--,j--
                
                为什么会是这三个表达式呢，因为在构造好的dp数组中，只存在三种情况，当前位置的最长公共子序列只由它的上边，左边，左上方得到
                我们判断最长公共子序列的时候也是只有三种情况，要么dp[i][j]=dp[i][j-1],要么dp[i-1][j-1],
                要么dp[i][j]=dp[i-1][j-1]+1，所以就对应了上述三种搜索情况。
    * */
    public String LCS (String s1, String s2) {
        int n=s1.length();
        int m=s2.length();
        //构造dp数组，dp[i][j]表示m的前i个字符和n的前j个字符的最长公共子序列的长度
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //如果对应位置的字符相等，那么s1的前i个字符和s2的前j个字符中，最长公共子序列的长度就是前一位置存储的最长公共子序列长度+1
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    //如果对应位置字符不相等，那么就最长公共子序列就是s1的前i个字符和s2的前j-1个字符中的最长公共子序列，
                    // 还有s1的前i-1个字符和s2的前j个字符中的最长公共子序列，两者取最大值
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        //法一：使用字符串拼接对象去拼接公共字符
//        if(dp[n][m]==0){
//            return "-1";
//        }
//        //定义一个字符串拼接对象
//        StringBuilder sb = new StringBuilder();
//        //从最后一个位置开始找
//        while(n>0 && m>0){
//            if(s1.charAt(n-1)== s2.charAt(m-1)){
//                //如果对应位置字符相等，那么就拼接
//                sb.append(s1.charAt(n-1));
//                //当前位置的最长公共子序列是由他左上方的结果+1得到的，我们逆推回去
//                n--;
//                m--;
//            }else{
//                //如果对应位置字符不相等，那么当前位置的长公共子序列的长度是由他的左边结果和上边结果，取最大值得到的，所以我们
//                //需要先判断左边和上边谁更大，然后就逆推到哪边
//                if(dp[n][m-1]>dp[n-1][m]){
//                    m--;
//                }else{
//                    n--;
//                }
//            }
//        }
//        return  sb.reverse().toString();
    
        //法二：借助栈，思想是一样的，把拼接换成了入栈
       //首先判断有没有公共子序列
        if(dp[n][m]==0){
            return "-1";
        }
        Stack<Character> stack=new Stack<>();
        //判断方式一：从对应字符是否相等的角度
//        while(n>0 && m>0) {
//            if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
//                //如果对应位置字符相等，那么就拼接
//                stack.push(s1.charAt(n - 1));
//                //当前位置的最长公共子序列是由他左上方的结果+1得到的，我们逆推回去
//                n--;
//                m--;
//            } else {
//                //如果对应位置字符不相等，那么当前位置的长公共子序列的长度是由他的左边结果和上边结果，取最大值得到的，所以我们
//                //需要先判断左边和上边谁更大，然后就逆推到哪边
//                if (dp[n][m - 1] > dp[n - 1][m]) {
//                    m--;
//                } else {
//                    n--;
//                }
//            }
//        }
        //判断方式二：从最长公共子序列的长度的角度
        while (dp[n][m]!=0){
            if(dp[n][m]==dp[n-1][m]){
                //说明最长公共子串的长度是由上边的结果得来的，往回推
                n--;
            }else if(dp[n][m]==dp[n][m-1]){
                //说明最长公共子串的长度是由左边得到的，往回推
                m--;
            }else if(dp[n][m]>dp[n-1][m-1]){
                //只有一种情况。说明最长公共子串的长度是由左上方得到的，只有这一种情况，那么就当前字符是相等的
                //往左上方推
                //先入栈
                stack.push(s1.charAt(n-1));
                n--;
                m--;
            }
        }
        String ret="";
        while (!stack.isEmpty()){
            ret+=stack.pop();
        }
        return  ret;
    }
}
